課程資訊
課程名稱
計算理論
Theory of Computing 
開課學期
108-2 
授課對象
管理學院  資訊管理學系  
授課教師
蔡益坤 
課號
IM3006 
課程識別碼
705 30400 
班次
 
學分
3.0 
全/半年
半年 
必/選修
選修 
上課時間
星期二7,8,9(14:20~17:20) 
上課地點
管二303 
備註
本課程中文授課,使用英文教科書。部份週次之週二6有實習,地點同上課教室。
總人數上限:50人
外系人數限制:8人 
Ceiba 課程網頁
http://ceiba.ntu.edu.tw/1082theory2020 
課程簡介影片
 
核心能力關聯
核心能力與課程規劃關聯圖
課程大綱
為確保您我的權利,請尊重智慧財產權及不得非法影印
課程概述

This is an introductory course to the theory of computing, a study of formal/mathematical foundations of computer science and technology. It covers various mathematical models, including automata and Turing machines, for physical computing machineries along with their computational capabilities/limitations. In terms of specific topics and the order of their exposition, the course will follow closely the book by Sipser. 

課程目標
The goal of this course is to acquaint the students with the basic concepts in computation theory and to cultivate the students' ability in analyzing the complexity of computational problems.
 
課程要求
待補 
預期每週課後學習時數
 
Office Hours
每週三 13:30~14:30
每週二 13:30~14:30 
指定閱讀
Introduction to the Theory of Computation, 3rd Edition, Michael Sipser, Cengage Learning, 2013. 
參考書目
See the course wiki site:
http://im.ntu.edu.tw/~tsay/dokuwiki/doku.php?id=courses:theory2020:main 
評量方式
(僅供參考)
 
No.
項目
百分比
說明
1. 
Homework 
20% 
 
2. 
Participation 
10% 
 
3. 
Midterm 
35% 
 
4. 
Final 
35% 
 
 
課程進度
週次
日期
單元主題
第1週
3/03  Introduction and Mathematical Preliminaries 
第2週
3/10  Introduction and Mathematical Preliminaries 
第3週
3/17  Finite Automata and Regular Languages 
第4週
3/24  Finite Automata and Regular Languages 
第5週
3/31  Finite Automata and Regular Languages
Context-Free Languages and Pushdown Automata 
第6週
4/07  Context-Free Languages and Pushdown Automata 
第7週
4/14  Context-Free Languages and Pushdown Automata 
第8週
4/21  Midterm Exam 
第9週
4/28  Turing Machines 
第10週
5/05  Turing Machines 
第11週
5/12  Decidability (and Undecidability) 
第12週
5/19  Reducibility 
第13週
5/26  Reducibility 
第14週
6/02  Time Complexity and NP-Completeness 
第15週
6/09  Time Complexity and NP-Completeness 
第16週
6/16  Final Exam 
第17週
6/23  More about NP-Completeness and Related Topics 
第18週
6/30  More about NP-Completeness and Related Topics